#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    //寻找矩阵目标值--数组批量排查
    bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) 
    {
        if(plants.size() == 0) return false;

        //记录最低行数，最右行
        //排除法，从第一行最后一个元素开始
        //由于每个元素都是从左往右、从上到下递增的
        //直接拿第一行或者第一列的最后一个元素开始枚举
        //小于目标值，直接排查一列；大于直接排查一行

        int maxrow = plants.size() - 1, maxcol = plants[0].size() - 1;
        int i = 0, j = maxcol;

        while(j >= 0 && i <= maxrow)
        {
            if(target < plants[i][j])
            {
                j--;
            }
            else if(target > plants[i][j])
            {
                i++;
            }
            else
            {
                return true;
            }
        }
        //没有找到
        return false;
    }
    //搜索旋转排序数组--二分
    int search(vector<int>& nums, int target) 
    {
        int n = nums.size();
        //没有元素/只有一个元素的情况
        if(n == 0) return -1;
        if(n == 1) return nums[0] == target ? 0 : -1;

        //先找有序的区间
        int left = 0, right = n - 1;
        while(left <= right)
        {
            int mid = (right - ((right - left) >> 1));

            if(nums[mid] == target) return mid;
            if(nums[0] < nums[mid]) //左边有序
            {
                if(nums[0] <= target && nums[mid] > target)
                {
                    //左边有序且目标值小于中间值，在左边开始找目标值
                    //一直缩小左区间
                    right = mid - 1;
                }
                else //右边有序或者无序，又变成子问题
                {
                    left = mid + 1;
                }
            }
            else //右边有序
            {
                if(nums[mid] < target && nums[n-1] >= target)
                {
                    //右边有序且目标值大于中间值
                    left = mid + 1;
                }
                else //右边有序或者无序，又变成子问题
                {
                    right = mid - 1;
                }
            }
        }
        //没有找到
        return -1;
    }
};


int main()
{
    return 0;
}